package com.code.test.dance;

import com.code.test.first.link.ListNode;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.md
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class Code24 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(6);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(5);
        ListNode n7 = new ListNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        ListNode tempHead = head;
        while (head != null) {
            System.out.print(head.getVal() + "→");
            head = head.getNext();
        }

        System.out.println("");

        ListNode node = swap2(tempHead);

        while (node != null) {
            System.out.print(node.val + "→");
            node = node.next;
        }
        System.out.println("");

    }

    public static ListNode swap2(ListNode head) {
        if (head == null) return null;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.setNext(head);

        ListNode cur = dummyNode;
        ListNode temp;
        ListNode first;
        ListNode second;
        while (cur != null && cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;

            first = cur.next;
            second = cur.next.next;
            //步骤一
            cur.next = second;
            //步骤二
            second.next = first;

            //步骤三
            first.next = temp;
            cur = first;

        }
        return dummyNode.next;
    }

    /**
     * 递归写法
     * next的next转向cur
     * cur的next转向下一个节点
     * 以此类推，最后面的先处理完，再把最新的第一个节点返回给上一轮递归
     * */
    public static ListNode swapNode(ListNode cur) {
        if (cur == null || cur.next == null) return cur;

        ListNode next = cur.next;
        ListNode newNode = swapNode(next.next);
        next.next = cur;
        cur.next = newNode;

        return next;
    }
}
